package com.topcoder.tccs411;

/**
 * An essential part of circuit design and general system optimization is 
 * critical path analysis. On a chip, the critical path represents the longest 
 * path any signal would have to travel during execution. In this problem we 
 * will be analyzing chip designs to determine their critical path length. 
 * The chips in this problem will not contain any cycles, i.e. there exists no 
 * path from one component of a chip back to itself.
 * 
 * Given a String[] connects representing the wiring scheme, and a String[] 
 * costs representing the cost of each connection, your method will return the 
 * size of the most costly path between any 2 components on the chip. In other 
 * words, you are to find the longest path in a directed, acyclic graph. 
 * Element j of connects will list the components of the chip that can be 
 * reached directly from the jth component (0-based). Element j of costs 
 * will list the costs of each connection mentioned in the jth element of 
 * connects. As mentioned above, the chip will not contain any cyclic paths. 
 * For example:
 * 
 * connects = {"1 2",
 *             "2",
 *             ""}
 * costs    = {"5 3",
 *             "7",
 *             ""}
 *             
 * In this example, component 0 connects to components 1 and 2 with costs 5 
 * and 3 respectively. Component 1 connects to component 2 with a cost of 7. 
 * All connections mentioned are directed. This means a connection from 
 * component i to component j does not imply a connection from component j 
 * to component i. Since we are looking for the longest path between any 2 
 * components, your method would return 12. 
 *
 */
public class Circuits {
	public int howLong(String[] connects, String[] costs) {
		int N = connects.length;
		int[][] g = new int[N][N];
		for (int i=0; i<N; i++) {
			String[] conn = connects[i].split(" ");
			String[] cost = costs[i].split(" ");
			for (int j=0; j<conn.length; j++) {
				if (conn[j].length() == 0) continue;
				int k = Integer.parseInt(conn[j]);
				g[i][k] = Integer.parseInt(cost[j]);
			}
		}
		
		int max = 0;
		for (int i=0; i<N; i++) {
			max = Math.max(max, dfs(g, i));
		}
		return max;
	}
	
	private int dfs(int[][] g, int i) {
		int max = 0;
		for (int j=0; j<g.length; j++) {
			if (g[i][j] > 0) {
				max = Math.max(max, g[i][j] + dfs(g, j));
			}
		}
		return max;
	}
}
